◀ Prev · Parts · Full · Next ▶

So by the chain rule, the probability of finding the min cut C is Pr [ C i = C ] ≥ ≥ ( n − − 2 n ) ( n − − 3 n − − 1 ) ( n − − 4 n − − 2 ) … … ( 3 5 ) ( 2 4 ) ( 1 3 ) . {\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}

Cancellation gives Pr [ C i = C ] ≥ ≥ 2 n ( n − − 1 ) {\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}} . Thus the probability that the algorithm succeeds is at least 1 − − ( 1 − − 2 n ( n − − 1 ) ) m {\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}} . For m = n ( n − − 1 ) 2 ln ⁡ ⁡ n {\displaystyle m={\frac {n(n-1)}{2}}\ln n} , this is equivalent to 1 − − 1 n {\displaystyle 1-{\frac {1}{n}}} . The algorithm finds the min cut with probability 1 − − 1 n {\displaystyle 1-{\frac {1}{n}}} , in time O ( m n ) = O ( n 3 log ⁡ ⁡ n ) {\displaystyle O(mn)=O(n^{3}\log n)} .

◀ Prev · Parts · Full · Next ▶